package leetcode.stack;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 150. 逆波兰表达式求值
 *
 */
public class EvalRPN {

    public static void main(String[] args) {
        EvalRPN solution = new EvalRPN();
        String[] srr = new String[]{"2", "1", "+", "3", "*"};
        Integer res = solution.evalRPN(srr);
        System.out.println(res);
    }

    /**
     * 逆波兰表达式求值
     *
     * 基本步骤
     *      从左至右扫描表达式, 遇到数字时, 将数字压入堆栈, 遇到运算符时, 弹出栈顶的两个数,
     * 		用运算符对它们做相应的计算(次顶元素和栈顶元素), 并将结果入栈, 重复上述过程直到表达式最右端
     *
     * @param tokens    字符串数组
     * @return
     */
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList<Integer>();
        int n = tokens.length;
        for (int i = 0; i < n; i++) {
            String token = tokens[i];
            if (isNumber(token)) {
                stack.push(Integer.parseInt(token));
            } else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (token) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                    default:
                }
            }
        }
        return stack.pop();
    }


    public boolean isNumber(String token) {
        return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
    }
}
